The present invention relates generally to automatically generating iterative and parallel control structures executable by a computer responsive to functions and operators that define requirements for a computer program in a high-level language. The present invention relates more specifically to repeatedly applying a normalize, transpose and distribute operation to the functions and operators until base cases are determined.
High-level functional languages, such as LISP and Haskell, are designed to bridge the gap between a programmer's concept of a problem solution and the realization of that concept in code. In these languages, a program consists of a collection of function definitions, roughly isomorphic to their counterparts in nonexecutable mathematical notation. The language semantics then generate the data and control structures necessary to implement a solution. A great deal of the complexity of execution remains hidden from the programmer, making it easier and faster to develop correct code.
The ease and reliability afforded by high-level languages often comes at a cost in terms of performance. Common wisdom says that if a software product must perform better in terms of speed and memory, it must be written in a lower level language, typically with arcane looking optimized assembly code at the extreme end.
Over time, however, the trend is for more software to be developed in higher level languages. There are two reasons for this. The first is immediately apparent; machine performance tends to improve over time, bringing more applications within the realm where high-level implementations, though perhaps slower than their low-level counterparts, are fast enough to get the job done. In other words the human costs in creating problem solutions are increasingly greater than the cost of the machines that carry them out.
The second reason is less apparent; while the intelligence of human programmers in writing low level algorithms remains roughly constant over time, the intelligence of automatic code generators and optimizers moves forward monotonically. Currently, we are beginning to see examples where a few lines of high-level code evaluated by a sophisticated general-purpose interpreter perform comparably to hand written, optimized code. This occurs because optimization is accomplished at the level of the compiler, rather than on individual programs, focusing the optimization efforts of the programming community in one place, where they are leveraged together on a reusable basis.